SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Random-access Turing machine</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Random-access Turing machine</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity</a>, a field of <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, <b>random-access Turing machines</b> extend the functionality of conventional <a href="Turing_machine" title="Turing machine">Turing machines</a> by introducing the capability for <a href="Random_access" title="Random access">random access</a> to <a href="Computer_memory" title="Computer memory">memory</a> positions. The inherent ability of RATMs to access any memory cell in a constant amount of time significantly decreases the computation time required for problems where data size and access speed are critical factors.<sup id="cite_ref-:1_1-0" class="reference"><a href="#cite_note-:1-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> As conventional Turing machines can only access data <a href="Sequential_access" title="Sequential access">sequentially</a>, the capabilities of RATMs are more closely with the memory access patterns of modern computing systems and provide a more realistic framework for analyzing <a href="Algorithm" title="Algorithm">algorithms</a> that handle the complexities of large-scale data.<sup id="cite_ref-:2_2-0" class="reference"><a href="#cite_note-:2-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>The random-access Turing machine is characterized chiefly by its capacity for <a href="Direct_memory_access" title="Direct memory access">direct memory access</a>: on a random-access Turing machine, there is a special <i><a href="Pointer_(computing)" class="mw-redirect" title="Pointer (computing)">pointer</a></i> tape of logarithmic space accepting a binary vocabulary. The Turing machine has a special state such that when the binary number on the <i>pointer</i> tape is 'p', the Turing machine will write on the working tape the <i>p</i>th symbol of the input. This attribute, which deviates from the <a href="Sequential_access" title="Sequential access">sequential memory access</a> inherent to standard Turing machines, allows RATMs to access any memory cell in a consistent and time-efficient manner. Notably, this characteristic of RATMs echoes the operation of contemporary computing systems featuring <a href="Random-access_memory" title="Random-access memory">random-access memory</a> (RAM). The formal model of RATMs enables the execution time of an instruction to be contingent upon the size of the numbers involved, bridging the gap between abstract computation models and real-world computational requirements.<sup id="cite_ref-:2_2-1" class="reference"><a href="#cite_note-:2-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>Additionally, the complexity and computational capacity of RATMs provide a framework for understanding the mechanics of computational theory. This model has been expanded to include both discrete and real-valued arithmetic operations, along with a finite precision test for real number comparisons.<sup id="cite_ref-:1_1-1" class="reference"><a href="#cite_note-:1-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> These extensions, including the universal random-access Turing machine (URATM),<sup id="cite_ref-:0_3-0" class="reference"><a href="#cite_note-:0-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> reflect the ongoing exploration of universal computation within the landscape of theoretical computer science.

</p>

<div class="mw-heading mw-heading2"><h2 id="Operational_efficiency">Operational efficiency</h2></div>

<p>The pointer tape facility lets the Turing machine read any letter of the input without taking time to move over the entire input, which is mandatory for complexity classes using less than <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a>.

</p><p>The comparison of RATMs with other computational models reveals that functions computable on a RAM in time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(t)}</annotation>

</semantics>

</math></span><img src="./2181f52974f20a5c4b5427d4898b3040ebaefbea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.422ex; height:2.843ex;" alt="{\displaystyle O(t)}" loading="lazy"></span> can be translated to a Turing machine computation time of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(t^{2}\cdot \log(t)\cdot \log \log(t))}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(t^{2}\cdot \log(t)\cdot \log \log(t))}</annotation>

</semantics>

</math></span><img src="./f98fc43e6f07cff12bf023268f89a00d9cd1fc00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.435ex; height:3.176ex;" alt="{\displaystyle O(t^{2}\cdot \log(t)\cdot \log \log(t))}" loading="lazy"></span>, and vice versa.<sup id="cite_ref-:2_2-2" class="reference"><a href="#cite_note-:2-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> This translation is indicative of the RATMs' robustness and versatility in handling a variety of computational tasks, particularly in large data scenarios. The random access capability of RATMs enhances data retrieval and manipulation processes, making them highly efficient for tasks where large datasets are involved. This efficiency is not just theoretical but has practical implications in the way algorithms are designed and executed in real-world computing environments.

</p>

<div class="mw-heading mw-heading2"><h2 id="Variants_and_extensions">Variants and extensions</h2></div>

<p>The theoretical landscape of RATMs has been significantly broadened by the advent of various variants and extensions. One extension is the universal random-access Turing machine (URATM), which has been instrumental in validating the existence and efficiency of universal computation within the random-access framework. This variant not only bolsters the computational capacity of RATMs but also serves as a tool in other theoretical investigations into computational complexity and universality.<sup id="cite_ref-:0_3-1" class="reference"><a href="#cite_note-:0-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Another extension is the formulation of quantum random-access Turing machines (QRATMs). These machines integrate the principles of <a href="Quantum_computing" title="Quantum computing">quantum computing</a> with the RATM framework, leading to a model that is more aligned with the architecture of modern quantum computers. QRATMs leverage properties of quantum mechanics, such as <a href="Quantum_superposition" title="Quantum superposition">superposition</a> and <a href="Quantum_entanglement" title="Quantum entanglement">entanglement</a>, to achieve computational capabilities that surpass those of classical RATMs. This quantum extension opens up new avenues in complexity analysis, offering more understanding of computational problems in a quantum context. Specifically, QRATMs have shed light on the relationships between quantum computational models and their classical counterparts, providing insights into the bounds and capabilities of quantum computational efficiency.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>RATMs have found application in the realm of big data computing, where their unique operational features facilitate exploration of both tractability and complexity. The ability of RATMs to execute operations in a time-bounded manner and provide random memory access makes them suitable for handling the challenges inherent in big data scenarios.<sup id="cite_ref-:2_2-3" class="reference"><a href="#cite_note-:2-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Traditional views on <a href="Computational_complexity_theory" title="Computational complexity theory">computational tractability</a>, typically defined within the realm of polynomial time, are often inadequate for addressing the massive scale of big data. RATMs, by contrast, enable a more nuanced approach, adopting sublinear time as a new standard for identifying tractable problems in big data computing.

</p><p>Moreover, the application of RATMs extends beyond just theoretical exploration; they provide a practical framework for developing algorithms and computational strategies tailored to the unique demands of big data problems. As big data continues to grow in both size and importance, the insights gained from studying RATMs have opened new avenues for research and practical applications in this field.<sup id="cite_ref-:2_2-4" class="reference"><a href="#cite_note-:2-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Computational_complexity_and_time–space_tradeoffs">Computational complexity and time–space tradeoffs</h2></div>

<p>The exploration of RATMs extends into the domain of <a href="Computational_complexity" title="Computational complexity">computational complexity</a> and <a href="Time%E2%80%93space_tradeoff" class="mw-redirect" title="Time–space tradeoff">time–space tradeoffs</a>, particularly in the context of nondeterministic computations.

</p><p>A key focus in this realm is the analysis of the inherent tradeoffs between time and space when solving computationally intensive problems. For instance, it is observed that certain computational problems, such as satisfiability, cannot be solved on general-purpose random-access Turing machines within specific time and space constraints. This indicates that there is a distinct tradeoff between the time taken to compute a function and the memory space required to perform the computation effectively. Specifically, results have shown that satisfiability cannot be resolved on these machines in time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{1.618}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{1.618}}</annotation>

</semantics>

</math></span><img src="./991544f7686d7a96b1cee99d213ef0b3de205035.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.372ex; height:2.676ex;" alt="{\displaystyle n^{1.618}}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{o(1)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{o(1)}}</annotation>

</semantics>

</math></span><img src="./2e9c58ecc77b8eb007fdc8af84ff291b3a5ae745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.526ex; height:2.843ex;" alt="{\displaystyle n^{o(1)}}" loading="lazy"></span>.<sup id="cite_ref-:3_5-0" class="reference"><a href="#cite_note-:3-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p><p>Additionally, the research explores how time–space tradeoffs affect nondeterministic linear time computations with RATMs, showing that certain problems solvable in nondeterministic linear time under specific space limits are infeasible in deterministic time and space constraints. This finding emphasizes the distinct computational behaviors of deterministic and nondeterministic models in RATMs, highlighting the need to consider time and space efficiency in algorithm design and computational theory.<sup id="cite_ref-:3_5-1" class="reference"><a href="#cite_note-:3-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Technical_and_Logical_Foundations">Technical and Logical Foundations</h2></div>

<p>The study of RATMs has been advanced through the exploration of <a href="Deterministic_system" title="Deterministic system">deterministic</a> <a href="Polylogarithmic_function" title="Polylogarithmic function">polylogarithmic</a> time and space and two-sorted logic, a concept explored in depth by recent research. This approach focuses on analyzing the efficiency and logical structure of RATMs, specifically how they can be optimized to perform computations in polynomial time with respect to the size of input data.

</p>

<div class="mw-heading mw-heading3"><h3 id="Deterministic_polylogarithmic_time_and_space">Deterministic polylogarithmic time and space</h3></div>

<p>Deterministic polylogarithmic time and space in RATMs refer to a computational efficiency where the time and space required for computation grow at a polylogarithmic rate with the size of the input data. This concept is pivotal in understanding how RATMs can be optimized for handling large data sets efficiently. It hypothesizes that certain computations, which previously seemed infeasible in polynomial time, can be executed effectively within this framework.<sup id="cite_ref-:4_6-0" class="reference"><a href="#cite_note-:4-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Two-sorted_logic">Two-sorted logic</h3></div>

<p>The use of two-sorted logic in the context of RATMs provides an approach to describing and analyzing computational processes. This framework involves distinguishing between two types of entities: numerical values and positions in data structures. By separating these entities, this approach allows for a more refined analysis of computational steps and the relationships between different parts of a data structure, such as arrays or lists. This methodology provides insights into the logical structure of algorithms, enabling a more precise understanding of their behavior. The application of two-sorted logic in RATMs significantly contributes to the field of <a href="Descriptive_complexity_theory" title="Descriptive complexity theory">descriptive complexity</a>.<sup id="cite_ref-:4_6-1" class="reference"><a href="#cite_note-:4-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBrattkaHertling1998" class="citation journal cs1">Brattka, Vasco; Hertling, Peter (1998-12-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcom.1998.0488">"Feasible Real Random Access Machines"</a>. <i>Journal of Complexity</i>. <b>14</b> (4): <span class="nowrap">490–</span>526. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcom.1998.0488">10.1006/jcom.1998.0488</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0885-064X">0885-064X</a>.</cite></span>

</li>

<li id="cite_note-:2-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-:2_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:2_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:2_2-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-:2_2-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-:2_2-4"><sup><i><b>e</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFCookReckhow1973" class="citation journal cs1">Cook, Stephen A.; Reckhow, Robert A. (1973-08-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2873%2980029-7">"Time bounded random access machines"</a>. <i>Journal of Computer and System Sciences</i>. <b>7</b> (4): <span class="nowrap">354–</span>375. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2873%2980029-7">10.1016/S0022-0000(73)80029-7</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-0000">0022-0000</a>.</cite></span>

</li>

<li id="cite_note-:0-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFGaoLiMiaoLiu2020" class="citation journal cs1">Gao, Xiangyu; Li, Jianzhong; Miao, Dongjing; Liu, Xianmin (2020-10-24). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/pii/S0304397520304072">"Recognizing the tractability in big data computing"</a>. <i>Theoretical Computer Science</i>. <b>838</b>: <span class="nowrap">195–</span>207. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1910.01357">1910.01357</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2020.07.026">10.1016/j.tcs.2020.07.026</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0304-3975">0304-3975</a>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFWangYing2023" class="citation journal cs1">Wang, Qisheng; Ying, Mingsheng (February 2023). "Quantum Random Access Stored-Program Machines". <i>Journal of Computer and System Sciences</i>. <b>131</b>: <span class="nowrap">13–</span>63. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/2003.03514">2003.03514</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2022.08.002">10.1016/j.jcss.2022.08.002</a>.</cite></span>

</li>

<li id="cite_note-:3-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-:3_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:3_5-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFFortnowvan_Melkebeek2000" class="citation book cs1">Fortnow, L.; van Melkebeek, D. (2000). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/856730">"Time-space tradeoffs for nondeterministic computation"</a>. <i>Proceedings 15th Annual IEEE Conference on Computational Complexity</i>. IEEE Comput. Soc. pp. <span class="nowrap">2–</span>13. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FCCC.2000.856730">10.1109/CCC.2000.856730</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7695-0674-6</bdi>.</cite></span>

</li>

<li id="cite_note-:4-6"><span class="mw-cite-backlink">^ <a href="#cite_ref-:4_6-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:4_6-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFFerrarottiGonzálezScheweTurull-Torres2022" class="citation journal cs1">Ferrarotti, Flavio; González, Senén; Schewe, Klaus-Dieter; Turull-Torres, José María (2022-04-07). <a rel="nofollow" class="external text" href="https://doi.org/10.3389%2Ffcomp.2022.845990">"Uniform Polylogarithmic Space Completeness"</a>. <i>Frontiers in Computer Science</i>. <b>4</b>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.3389%2Ffcomp.2022.845990">10.3389/fcomp.2022.845990</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/2624-9898">2624-9898</a>.</cite></span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-17" href="https://en.wikipedia.org/wiki/?title=Random-access_Turing_machine&oldid=1296039617">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>